package org.simon;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @description: <a href="https://leetcode.cn/problems/course-schedule/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj">207. 课程表</a>
 * @author: zhaoyinglin
 * @date: 2024/3/15
 */
public class CourseSchedule {

    public static void main(String[] args) {

        int[][] array = new int[][] {
                { 1, 4 }, { 2, 4 }, { 3, 1 }, { 3, 2 }
        };

        Solution solution = new Solution();

        System.out.println(solution.canFinish(5, array));

    }

    static class Solution {
        // 节点的入度: 使用数组保存每个节点的入度,
        public boolean canFinish(int numCourses, int[][] prerequisites) {

            // 课程依赖关系存储，比如 [1, 0] 表示 课程1依赖于课程0，存储 样式 {1:[0]}
            Map<Integer, Set<Integer>> courseRelation = new HashMap<>();
            // 1. 初始化数据 假设所有节点都没有依赖
            for (int i = 0; i < numCourses; i++) {
                courseRelation.put(i, new HashSet<>());
            }

            // 2. 构建依赖关系
            for (int[] pre : prerequisites) {

                int cur = pre[0];

                int related = pre[1];

                Set<Integer> relatedCourse = courseRelation.get(cur);

                relatedCourse.add(related);

                courseRelation.put(cur, relatedCourse);
            }

            // 3. 获取没有依赖的课程，先行修掉
            List<Integer> canFinishCourse = new ArrayList<>();
            Set<Integer> visitedCourse = new HashSet<>();
            // 先获取所有没有依赖的课程
            for (Integer key : courseRelation.keySet()) {
                if (courseRelation.get(key).isEmpty()) {
                    canFinishCourse.add(key);
                    visitedCourse.add(key);
                }
            }

            // 4. 循环遍历，将依赖课程数进行更新
            // 比如: canFinishCourse = [0]
            // courseRelation ==> {1 : [0]} 遍历完成后 courseRelation ==> {1 : []}
            while (!canFinishCourse.isEmpty()) {

                // 先获取所有没有依赖的课程
                for (Map.Entry<Integer, Set<Integer>> entry : courseRelation.entrySet()) {
                    Set<Integer> course = entry.getValue();
                    if (course.isEmpty()) {
                        continue;
                    }
                    for (Integer c : canFinishCourse) {
                        course.remove(c);
                    }
                }

                canFinishCourse = new ArrayList<>();

                // 先获取所有没有依赖的课程
                for (Integer key : courseRelation.keySet()) {
                    if (courseRelation.get(key).isEmpty() && !visitedCourse.contains(key)) {
                        canFinishCourse.add(key);
                        visitedCourse.add(key);
                    }
                }
            }

            return visitedCourse.size() == numCourses;
        }
    }

}
